題目

https://leetcode.com/problems/linked-list-cycle-ii/

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, 
where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, 
where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:

Can you solve it without using extra space?

解答

C#

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head) {
        try
        {
            if (head == null)
                return head;

            var oneStep = head;
            var twoStep = head;
            while (oneStep.next != null && twoStep.next != null)
            {
                oneStep = oneStep.next;
                twoStep = twoStep.next.next;
                if (oneStep == twoStep)
                {
                    var oneStep2 = head;
                    while (oneStep.next != null && oneStep2.next != null)
                    {
                        if (oneStep == oneStep2)
                            return oneStep;

                        oneStep = oneStep.next;
                        oneStep2 = oneStep2.next;
                    }
                }

            }
            return null;
        }
        catch (Exception)
        {
            return null;
        }
    }
}

結果

Runtime: 84 ms, faster than 100% of C# online submissions.

Memory Usage: 24.8 MB, less than 33.33% of C# online submissions.

Time Complexity: O(n) ~ O(n^2)

Space Complextiy: O(n)

為什麼我要這樣做？

還記得昨天的 141. Linked List Cycle 嗎？這題幾乎長得一模一樣，是延伸題喔～
主要是找出是哪個 node 讓整個 linked list 呈現 cycle 樣子。

忘記的人請參考↓
[Day 14] 演算法刷題 LeetCode 21. Merge Two Sorted Lists (Easy)
[Day 15] 演算法刷題 LeetCode 141. Linked List Cycle (Easy)

1. 解法跟 141. Linked List Cycle 一樣，先判斷出是否為 cycle，這邊我就不再贅述
   • 若是 cycle
     • 則宣告另一個 oneStep2 從 head 開始一步一步走起
     • 宣告第二層 while 迴圈去找出 oneStep 及 oneStep2 的交會點(node)，則為 cycle begin (node)
   • 若不是 cycle
     • return null
2. Error handling，以防出現 Runtime Exception，並return null

為什麼可以確保 oneStep 及 oneStep2 可以交會呢? 要先從 oneStep 及 TwoStep 交會點開始推論！以下圖表為例

由上圖表得知 7 為 oneStep 及 twoStep 的交會點，代稱為x

假設

1. head 到 cycle begin(node) 的距離為 a
2. cycle begin(node) 到 x 的距離為 b
3. x 到 cycle begin(node) 的距離為 c

在找到 x 時

1. oneStep 走了 a + b 的距離
2. twoStep 走了 a + b + c + b = a + 2b + c 的距離

twoStep 是 oneStep 的兩倍速度，所以可以推論
=> 2 ( a + b ) = a + 2b + c
=> 2a + 2b = a + 2b +c
=> 2a = a + c
=> a = c

也因為這樣就可以推論，當

1. oneStep 從 x 開始走起
2. oneStep2 從 head 開始走起

絕對會在 cycle begin(node) 交會，也就找到cycle begin(node) 在哪啦！

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉